package bts_list;

import bin_tree.MyBinTree.BinTreeNode;

public class Main {
    public static BinTreeNode increasingBST(BinTreeNode root) {
        if (root == null) {
            return null;
        }
        BinTreeNode leftHead = increasingBST(root.left);
        root.left = null;
        BinTreeNode leftNode = leftHead;
        while (leftNode != null && leftNode.right != null) {
            leftNode = leftNode.right;
        }
        if (leftNode != null) {
            leftNode.right = root;
        }
        BinTreeNode rightHead = increasingBST(root.right);

        root.right = rightHead;
        return leftHead != null ? leftHead : root;
    }

    public static void main(String[] args) {
        BinTreeNode nodeA = new BinTreeNode('A');
        BinTreeNode nodeB = new BinTreeNode('B');
        BinTreeNode nodeC = new BinTreeNode('C');
        BinTreeNode nodeD = new BinTreeNode('D');
        nodeA.left = nodeB;
        nodeA.right = nodeD;
        nodeB.right = nodeC;
        BinTreeNode node = increasingBST(nodeA);
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.right;
        }
    }
}
